package com.sicheng.lc.周赛.分类.贪心;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/11 15:39
 */
public class 最小差值平方和 {
    //https://leetcode.cn/problems/range-sum-of-sorted-subarray-sums/
    public long minSumSquareDiff(int[] a, int[] nums2, int k1, int k2) {
        long sum = 0;
        long ans = 0;
        int n = a.length;
        for (int i = 0; i < a.length; i++) {
            a[i] = Math.abs(a[i] - nums2[i]);
            sum += a[i];
            ans += (long) a[i] * a[i];
        }
        int k = k1 + k2;
        //heap(nums1,k);
        if (k >= sum)
            return 0;

        Arrays.sort(a);
        for (int i = n - 1; ; --i) {
            int m = n - i;
            long v = a[i], c = m * (v - (i > 0 ? a[i - 1] : 0));
            ans -= v * v;
            if (c <= k) {
                k -= c;
                continue;
            }
            v -= k / m;
            return ans + k % m * (v - 1) * (v - 1) + (m - k % m) * v * v;
        }

    }


    // 此做法复杂度较高 O(k1+k2)*O(logN)
    private long heap(int[] nums, int k) {
        heap(nums);
        while (nums[0] > 0 && k > 0) {
            nums[0]--;
            k--;
            shiftDown(nums, 0, nums[0]);
        }
        long res = 0;
        for (int i : nums) {
            res += (long) i * i;
        }
        return res;
    }


    void heap(int[] nums) {
        for (int i = (nums.length >> 1) - 1; i >= 0; i--) {
            shiftDown(nums, i, nums[i]);
        }
    }


    void shiftDown(int[] nums, int k, int e) {
        int half = nums.length >>> 1;
        while (k < half) {
            int c = k << 1 | 1;
            if (c + 1 < nums.length && nums[c + 1] > nums[c])
                c++;

            if (nums[c] <= e)
                break;

            nums[k] = nums[c];
            k = c;

        }
        nums[k] = e;
    }

}
